package com.leetcode.partition5;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/8/21 10:44
 */
public class LC450删除二叉搜索树中的节点 {

    public static TreeNode deleteNode(TreeNode root, int key) {
        return delete(root, key);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3), new TreeNode(10, new TreeNode(7), new TreeNode(11)));
        root = deleteNode(root, 7);
        System.out.println(root.val);
    }

    /**
     * 删除二叉搜索树中的节点 情况1、当key的节点度为1或0：直接返回非空的唯一子节点 情况2、当key的节点度为2：找到前驱节点，将前驱节点的值赋值给当前结点，并向左递归删除前驱节点（转化为了情况1）
     */
    private static TreeNode delete(TreeNode cur, int key) {
        if (cur == null)
            return null;
        if (cur.val > key) {
            cur.left = delete(cur.left, key);
        } else if (cur.val < key) {
            cur.right = delete(cur.right, key);
        } else if (cur.left != null && cur.right != null) {
            // 找到被删除节点，但是当前结点的度为2，因此需要找到前驱节点，将前驱节点的值赋值给当前节点，并递归删除前驱结点
            TreeNode pre = predecessor(cur);
            cur.val = pre.val;
            cur.left = delete(cur.left, pre.val); // 转化为删除前驱节点
        } else {
            // 被删除节点的度为1或0，只需要返回非空子节点
            return cur.left == null ? cur.right : cur.left;
        }
        return cur;
    }

    /**
     * 寻找前驱节点
     */
    private static TreeNode predecessor(TreeNode root) {
        TreeNode pre = root.left;
        while (pre.right != null)
            pre = pre.right;
        return pre;
    }

    // ------------------迭代法-----------------

    private static TreeNode iteration(TreeNode root, int key) {
        if (root == null)
            return null;
        TreeNode cur = root, pre = null;
        while (cur != null) {
            if (cur.val == key)
                break; // cur指向的就是被删除节点
            pre = cur;
            if (cur.val > key)
                cur = cur.left;
            else
                cur = cur.right;
        }
        if (pre == null)
            return delete(cur); // BST树只有一个根结点
        if (pre.left == cur) {
            pre.left = delete(cur);
        } else if (pre.right == cur) {
            pre.right = delete(cur);
        }
        return root;
    }

    private static TreeNode delete(TreeNode cur) {
        if (cur == null)
            return null;
        if (cur.right == null)
            return cur.left;
        TreeNode successor = cur.right;
        while (successor.left != null)
            successor = successor.left;
        successor.left = cur.left;
        return cur.right;
    }
}
